Arrays & Hashing

217 Contains Duplicate

Let n be the number of elements in the nums list.

Time Complexity: We iterate through the list once. Each membership check (i in counter) and insertion into the set takes O(1) on average. In the worst case—when all elements are unique—we perform these operations n times, resulting in O(n) time.

Space Complexity: The extra space used comes from the set counter. In the worst case (all elements are unique), the set stores all n elements, so the space complexity is O(n).

#217
from typing import List

def containsDuplicate(nums: List[int]) -> bool:
    counter = set()
    for num in nums:
      if num in counter:
        return True
      counter.add(num)
    return False

#include <vector>
#include <unordered_set>

bool containsDuplicate(std::vector<int>& nums){
  std::unordered_set<int> memo = {};

  for(auto num: nums){
    if(memo.find(num) != memo.end()){
      return true;
    }
    memo.insert(num);
  }

  return false;
};

242 Valid Anagram

Time Complexity: We compare the lengths of s and t. This takes O(1) time. If the lengths differ, the strings cannot be anagrams. If the lengths are equal, let the common length be n. We iterate once through both strings to build two hashmaps that count the frequency of each character. This takes O(n) time. Comparing the two hashmaps also takes O(n) time in the worst case. Overall, the time complexity is O(n).

Space Complexity: The extra space comes from the two hashmaps used to store character frequencies. In the worst case, each character in the string is unique, so the hashmaps store up to n entries. Since we ensure the strings have equal length before counting, the space complexity is O(n).

def isAnagram(s: str, t:str) -> bool:

  if len(s) != len(t):
    return False
  
  s_map, t_map = {}, {}

  for i in range(len(s)):
    s_map[s[i]] = 1 + s_map.get(s[i], 0)
    t_map[t[i]] = 1 + t_map.get(t[i], 0)

  return s_map == t_map

bool isAnagram(std::string s, std::string t){
  if(s.length() != t.length()){
    return false;
  }

  std::unordered_map<char, int> countS;
  std::unordered_map<char, int> countT;
  for(int i = 0; i < s.length(); i++){
    countS[s[i]]++;
    countT[t[i]]++;
  }

  return countS == countT; 
};

bool isAnagram(std::string s, std::string t){
  if(s.length() != t.length()){
    return false;
  }

  std::vector<int> count(26, 0);

  for(int i = 0; i < s.length(); i++){
    count[s[i] - 'a']++;
    count[t[i] - 'a']--; 
  }

  for(int i: count){
    if(i != 0)
      return false;
  }

  return true;
};

1 Two Sum

Let n be the number of elements in the nums list.

Time Complexity: We iterate through the list once. For each element, we compute the difference target - num and check whether the current number has already been seen as a needed difference. Dictionary lookups and insertions take O(1) on average, so the overall time complexity is O(n).

Space Complexity: the extra space comes from the dictionary used to store previously seen differences and their indices. In the worst case—when no solution is found until the end—the dictionary stores up to n entries, resulting in O(n) space complexity.

def twoSum(nums: List[int], target: int) -> List[int]:
  diffs = {}
  for idx, num in enumerate(nums):
    diff = target - num
    if num in diffs:
      return [diffs[diff], idx]
    diffs[diff] = idx

49 Group Anagrams

Let n be the number of strings in strs, and let k be the maximum length of a string.

Time Complexity: We iterate through the list of strings once, which takes O(n) time. For each string, we sort its characters to generate a key. Sorting a string of length k takes O(k log k) time. Therefore, the total time complexity is O(n * k * log(k)). Converting the hash map values to a list at the end takes O(n) time in total, which does not change the overall complexity. Overall the time complexity is O(n * klog(k))

Space Complexity"

We use a hash map to group strings by their sorted character keys. In the worst case, all strings are unique and each forms its own group. The total extra space used to store the groups and keys is O(n · k), where n is the number of strings in str and k is the length of the longest string.

from typing import List
from collections import defaultdict


def groupAnagrams(strs: List[str]) -> List[List[str]]:
    res = defaultdict(list)

    for word in strs:
        key = "".join(sorted(word))
        res[key].append(word)
    return list(res.values())

347 Top K Frequent Elements

from collections import defaultdict


def topKFrequent(nums: List[int], k: int) -> List[int]:
  memo = defaultdict(int)
  for num in nums:
    memo[num] += 1
  
  sorted_dict = sorted(memo.items(), key=lambda item: item[1], reverse=True)

  return [item[0] for item in sorted_dict[:k]]

?Encode and Decode Strings

def encode(strs: List[str]) -> str:
  for idx in range(len(strs)):
    strs[idx] = f"{str(len(strs[idx]))}#{strs[idx]}"
  return "".join(strs)
     
def decode(s: str) -> List[str]:
  res = []
  r = 0
  while r < len(s):
    l = r
    while s[r] != "#":
      r += 1
    
    length = int(s[l:r])
    l = r + 1
    r = l + length

    res.append(s[l:r])
  
  return res

238 Product of Array Except Self

import copy

def productExceptSelf(nums: List[int]) -> List[int]:
  forward = copy.deepcopy(nums)
  backward = copy.deepcopy(nums)

  for i in range(1, len(nums)):
    forward[i] *= forward[i - 1] 
    backward[-i - 1] *= backward[-i]
  
  forward = forward[:-1]
  backward = backward[1:]
  
  for i in range(1, len(backward)):
    backward[i] *= forward[i - 1]
  
  backward.append(forward[-1])
  return backward

36 Valid Sudoku

Time Complexity: O(n²). We scan each cell exactly once across an n×n board. For each filled cell, we perform a constant number of hash-set lookups and insertions (row, column, and 3×3 box), each O(1) on average.

Space Complexity: O(n²). In the worst case, we may store up to n values for each of the n rows, n columns, and n sub-boxes. This is still O(n²) overall (constants ignored).

def isValidSudoku(board: List[List[str]]) -> bool:
  rows_memo = defaultdict(set)
  cols_memo = defaultdict(set)
  squares_memo = defaultdict(set)

  for row_num, row in enumerate(board):
    for col_num, elem in enumerate(row):
      if elem == '.':
        continue

      if elem in rows_memo[row_num]:
        return False
      else:
        rows_memo[row_num].add(elem)
      
      if elem in cols_memo[col_num]:
        return False
      else:
        cols_memo[col_num].add(elem)
      
      if elem in squares_memo[(row_num // 3, col_num // 3)]:
        return False
      else:
        squares_memo[(row_num // 3, col_num // 3)].add(elem)
      
  return True

128 Longest Consecutive Sequence

Let n be the number of elements in the nums list.

Time Complexity: O(n). Converting the list to set takes O(n) time, checking each element takes O(n) time.

Space Complexity: O(n). The only extra space used is for converting the nums list to set, takes at most O(n) space.

def longestConsecutive(nums: List[int]) -> int:
  nums_set = set(nums)

  # The first term of the sequence should not have any adjacent term that is smaller than it.
  # If 5 is the start of a sequence, 4 should not exist or else 5 would not be the start of the sequence
  # We can check only the start of a sequence and record the longest sequence
  
  res = 0
  for num in nums_set:
    if num - 1 in nums_set:
      continue
    else:
      count = 1
      while num + 1 in nums_set:
        count += 1
        num += 1
      res = res if res > count else count
  return res